/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.graph;
import java.util.*;
import java.util.Map.Entry;

/**
 * 
 * A node of the prefix tree
 * 
 * @author Philippe Bordron
 * 
 * @param <E> : class of the value stored in each node
 */
public class PrefixTreeNode<E>{

	protected E val; // value stored in the node
	protected Map<E,PrefixTreeNode<E>> successors; // successors of the node
	protected PrefixTreeNode<E> predecessor; // predecessor of the node
	
	
	/**
	 * create a PrefixTreeNode tree with the value val and it son of father
	 * @param val
	 * @param father
	 */
	public PrefixTreeNode(E val, PrefixTreeNode<E> father)
	{
		this.val = val;
		this.successors = new HashMap<E, PrefixTreeNode<E>>();
		this.predecessor = father;
	}
	
	/**
	 * Clear each PrefixTreeNodes that is a successor of this one
	 */
	public void clear()
	{
		for (Entry<E, PrefixTreeNode<E>> entry : successors.entrySet())
		{
			entry.getValue().clear();
		}
		successors.clear();
	}
	
	/**
	 * Get the value stored in the node
	 * @return
	 */
	public E getVal()
	{
		return val;
	}

	/**
	 * Get successors of the current node
	 * @return a collection of nodes
	 */
	public Collection<PrefixTreeNode<E>> getChilds()
	{
		return successors.values();
	}
	
	/**
	 * Get the father of the current note
	 * @return a PrefixeTreeNode
	 */
	public PrefixTreeNode<E> getFather()
	{
		return this.predecessor;
	}

	/**
	 * Get the successor that contains the value e
	 * @param e
	 * @return a node
	 */
	public PrefixTreeNode<E> getSon(E e)
	{
		return this.successors.get(e);
	}
	
	
	public void setFather(PrefixTreeNode<E> f)
	{
		this.predecessor = f;
	}
	
	public void removeSon(PrefixTreeNode<E> f)
	{
		successors.remove(f);
	}
 
	public void addSon(PrefixTreeNode<E> n)
	{
		successors.put(n.val, n);
	}

	/**
	 * Tests if the current node have a predecessor
	 * @return true if the node is a root (false else)
	 */
	public boolean isRoot()
	{
		return predecessor == null;
	}
	
	/**
	 * Test if the current node has some successors.
	 * @return true if the are no successor (false else)
	 */
	public boolean isLeaf()
	{
		return successors == null || successors.isEmpty();
	}
	
	/**
	 * Get the deviation node between the successors of the current node and a path
	 * @param prefixe
	 * @return
	 */
	public PrefixTreeNode<E> getDeviationNode(ListIterator<E> prefixe)
	{
		// retoune le noeud de divergence
		E n;
		if (prefixe.hasNext() && successors.containsKey(n = prefixe.next()))
		{
			PrefixTreeNode<E> elem = successors.get(n);
			return elem.getDeviationNode(prefixe);
		}
		return this;
	}

	/**
	 * Add the Path s to the current PrefixeTree(Node)
	 * @param s a path
	 * @return the deviation node
	 */
	public PrefixTreeNode<E> addSequence(ListIterator<E> s)
	{
		PrefixTreeNode<E> elem;
		if(s.hasNext())
		{
			E n = s.next();
			if (successors.containsKey(n))
			{
				elem = successors.get(n);
				return elem.addSequence(s);
			}
			else
			{
				elem = new PrefixTreeNode<E>(n, this);
				successors.put(n,elem);
				elem.addSequence(s);
				return this;
			}
		}
		return this;
	}
	
	
	
	/**
	 * remove the Path s from the current PrefixeTree(Node)
	 * @param s
	 * @return
	 */
	public boolean removeSequence(ListIterator<E> s)
	{
		if(successors.isEmpty())
		{
			return true;
		}
		E n;
		if (s.hasNext() && successors.containsKey(n = s.next()))
		{
			PrefixTreeNode<E> elem = successors.get(n);
			boolean estFeuille = elem.removeSequence(s);
			if (estFeuille)
			{
				successors.remove(elem.getVal());
			}
			return estFeuille && successors.size() == 0;
		}	
		return false;
	}
	
	/**
	 * Tranforms the PrefixTree to a collection of path
	 * @return
	 */
	public Collection<List<E>> toPaths()
	{
		Collection<List<E>> result;
		result = new LinkedList<List<E>>();
		if (this.isLeaf())
		{
			LinkedList<E> l = new LinkedList<E>();
			l.addFirst(val);
			result.add(l);
		}
		for (PrefixTreeNode<E> n : successors.values())
		{
			for (List<E> seq : n.toPaths())
			{
				((LinkedList<E>)seq).addFirst(val);
				result.add(seq);
			}
		}
		return result;
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((val == null) ? 0 : val.hashCode());
		return result;
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof PrefixTreeNode))
			return false;
		PrefixTreeNode<?> other = (PrefixTreeNode<?>) obj;
		if (val == null) {
			if (other.val != null)
				return false;
		} else if (!val.equals(other.val))
			return false;
		return true;
	}

	public String toString()
	{
		return val.toString();
	}
	
	public String toString(int p)
	{
		String res = "";
		for (int i=0; i<p;i++)
		{
			res = res + "\t";
		}
		res = res + this.toString() + "\n";
		for(PrefixTreeNode<E> n : successors.values())
		{
			res = res + n.toString(p+1);
		}
		return res;
	}
	
}